GATE CSE 2003
Q11.
In a permutation a_1.....a_n of n distinct integers, an inversion is a pair (a_i, a_j) such that i \lt j and a_i \gt a_j. If all permutation are equally likely, what is the expected number of inversions in a randomly chosen permutation of 1.....n?Q12.
Let \Sigma = (a, b, c, d, e) be an alphabet. We define an encoding scheme as follows : g(a) = 3, g(b) = 5, g(c) = 7, g(d) = 9, g(e) = 11. Let p_{i} denote the i-th prime number (p_{i}=2). For a non-empty string s=a_{1}...a_{n}, where each a_{i} \in \Sigma, define f(i)=\prod_{i=1}^{n}{P_{i}}^{g(a_{i})}. For a non-empty sequence < s_{j},...,s_{n} > of strings from \Sigma^{+}, define h(<s_{i}...s_{n} >)=\prod_{i=1}^{n}{P_{i}}^{f(s_{i})} Which of the following numbers is the encoding, h, of a non-empty sequence of strings?Q13.
If the strings of a language L can be effectively enumerated in lexicographic (i.e. alphabetic) order, which of the following statements is true?Q15.
Let G = ({S}, {a, b} R, S) be a context free grammar where the rule set R is S\rightarrow aSb|SS|\epsilon Which of the following statements is true?Q16.
Consider the grammar shown below. S \rightarrow C C C \rightarrow cC | d The grammar isQ17.
The following are the starting and ending times of activities A,B,C,D,E,F,G and H respectively in chronological order: a_{s}\; b_{s} \; c_{s}\;a_{e}\;d_{s}\;c_{e}\;e_{s}\;f_{s}\;b_{e}\;d_{e}\;g_{s}\;e_{e}\;f_{e}\;h_{s}\;g_{e}\;h_{e} . Here, x_{s} denotes the starting time and x_{e} denotes the ending time of activity X. W need to schedule the activities in a set of rooms available to us. An activity can be scheduled in a room only if the room is reserved for the activity for its entire duration. What is the minimum number of rooms required?Q18.
Let : A\rightarrowB be injective (one-to-one) function. Define g:2^{A}\rightarrow 2^{B} as: g(C) = {f (x)| x \inC), for all subsets C of A. Defineg:2^{B}\rightarrow 2^{A} as : h(D) = {x | x \in A, f (x) \in D}, for all subsets D of B. Which of the following statements is always true?Q19.
Consider the following graph Among the following sequences (I) a b e g h f (II) a b f e h g (III) a b f h g e (IV) a f g h b e Which are depth first traversals of the above graph?Q20.
Consider the set \Sigma ^{*} of all strings over the alphabet \Sigma ={0,1}. \Sigma ^{*} with the concatenation operator for strings